package solutions;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-29
 * Time: 13:12
 */


//https://leetcode.cn/problems/flood-fill/submissions/397712739/
    //dfs递归
    //bfs队列
class Solution {
    //深度优先搜索dfs
    //利用数组实现坐标的右下上左的移动
    int[] dx = {1, 0, 0, -1};//x轴
    int[] dy = {0, 1, -1, 0};//y轴

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int currColor = image[sr][sc];
        if (currColor != color) {
            dfs(image, sr, sc, currColor, color);
        }
        return image;
    }

    //dfs
    public void dfs(int[][] image, int x, int y, int currColor, int color) {
        if (image[x][y] == currColor) {
            image[x][y] = color;
            for (int i = 0; i < 4; i++) {//通过遍历i来改变坐标
                int mx = x + dx[i];
                int my = y + dy[i];
                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
                    dfs(image, mx, my, currColor, color);//递归处理
                }
            }
        }
    }
}

//class Solution {
//    //广度优先搜索bfs
//    //利用数组实现坐标的右下上左的移动
//    int[] dx = {1, 0, 0, -1};//x轴
//    int[] dy = {0, 1, -1, 0};//y轴
//
//    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//        int currColor = image[sr][sc];
//        if (currColor == color) {
//            return image;
//        }
//        //利用队列的性质，实现bfs
//        Deque<int[]> queue = new LinkedList<>();
//        queue.offer(new int[]{sr, sc});
//        image[sr][sc] = color;
//        while (!queue.isEmpty()) {
//            int[] cell = queue.poll();
//            for (int i = 0; i < 4; i++) {
//                int mx = cell[0] + dx[i];
//                int my = cell[1] + dy[i];
//                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length
//                        && image[mx][my] == currColor) {
//                    queue.offer(new int[]{mx, my});
//                    image[mx][my] = color;
//                }
//            }
//        }
//        return image;
//    }
//}